
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>深入解析快速排序(Quick Sort) - Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="本文深入分析了快速排序(Quick Sort)的原理、实现，包括三数取中、混合排序等">
  <meta name="keywords" content="快速排序 QuickSort 三数取中 混合排序 插入排序 stl sort qsort">

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/blog/2016/03/09/quicksort/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">深入解析快速排序(Quick Sort)</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-03-09T22:34:14+08:00'><span class='date'><span class='date-month'>Mar</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:34 pm</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><p>本文将对快速排序进行深入的分析和介绍。通过学习本文，您将</p>

<blockquote>
  <ul>
    <li>秒杀快速排序面试</li>
    <li>掌握高效实现快排</li>
    <li>加深范型编程意识</li>
  </ul>
</blockquote>

<h2 id="section">八卦花絮</h2>

<p>快速排序是由图灵奖获得者、计算机语言设计大佬C. A. R. Hoare在他26岁时提出的。说起C. A. R. Hoare老爷爷，可能很多人的第一印象就是快速排序，但是快排仅仅是他人生中非常小的成就而已。例如，他在1978年提出的Communicating Sequential Processes(CSP)理论，则深深的影响了并行程序设计，Go语言中的Goroutine就是这种典范。</p>

<!--more-->

<h2 id="section-1">基本思想</h2>

<p>快速排序的思想非常简单：对于一个数组S，我们选择一个元素，称为pivot。将数组S中小于等于pivot的元素放在S的左边，大于等于pivot的元素放在S的右边。左右两部分分别记为S1和S2，然后我们递归的按上述方式对S1、S2进行排序。</p>

<p>具体说来，我们维护两个指针，采用两边扫描。从左到右扫描，当遇到一个元素大于等于pivot时，暂停。从右到左扫描，当遇到一个小于等于pivot元素时，暂停。然后交换这两个元素。继续扫描，直到两个指针相遇或者交叉。</p>

<p>从直观上看，每次递归处理的两个子数组S1、S2的大小最好是相等或者接近的，这样所花费的时间最少。</p>

<h2 id="section-2">实现细节</h2>

<p>说起来容易，做起来难了。要想正确实现快速排序非常不容易，很容易犯错。简单的修改就可能导致程序死循环或者结果错误。如果你一度感到很难在几分钟内实现一个正确的快速排序，说明你是正常人。那些五分钟内就能把快速排序写对的，几乎都是背代码。</p>

<p>我在实现以下代码时，就反复调试了十几分钟。而且，我会告诉你曾经JDK的某个版本实现中都存在bug么？</p>

<p>在给出完整代码之前，我们来考虑几个非常重要的问题。</p>

<h3 id="pivot">如何选择pivot？</h3>

<p>至少有几种显而易见的方法：</p>

<p>尝试1:选择数组中的第一个元素。成本低，但是当输入数组已经有序时，将导致O($n^2$)的复杂度。例如S={1,2,3,4,5,6,7,8,9}，如果选择第一个元素也就是1作为pivot，那么S1={1}, S2={2,3,4,5,6,7,8,9}，两个子数组非常的不平衡。当递归对S2排序时，选择2也就是S2中第一个元素作为pivot排序时，又会将S2分成两个极其不平衡的子数组。经过简单分析可知，此时算法复杂度为O($n^2$)。因此这不是一个理想、健壮的方法。</p>

<p>尝试2:随机选择一个。这种方法一般都能很好work，但是随机子程序可能非常昂贵，这可能拖慢整个程序。</p>

<p>尝试3:取中位数。取中位数可以保证S的两个子数组是等大小的（或者相差1），但是计算中位数可不是一个轻轻松松的活儿，将会严重拖慢算法速度。</p>

<p>尝试4:三数取中。尝试3方法太昂贵，我们可以稍微改变下：取数组第一个元素、最后一个元素、中间元素这三个元素的中位数。</p>

<h3 id="section-3">遇到相等的元素怎么办？</h3>

<p>左右扫描，如果遇到和pivot相等的元素怎么办？是暂停扫描还是继续扫描？</p>

<p>首先，两个方向采取的策略应该是一样的，也就是要么都暂停（然后交换），要么都继续扫描。否则将导致两个子数组不平衡。</p>

<p>其次，为了更好分析这个问题，我们不妨考虑所有元素都相同的情形。如果我们遇到和pivot相等的时候不停止，那么从左到右扫描时，两指针将相遇，此次过程结束。结果呢？什么都没做，却得到了两个大小极其不均衡的数组。算法时间复杂度为O($n^2$)。如果我们选择遇到相等元素时停止扫描，然后交换，那么虽然看上去交换的次数变多了，但是我们将得到大小相等（或者差1）的两个子数组。算法的时间复杂度为O($nlgn$)。</p>

<p>因此，遇到和pivot相等的元素时候我们都暂停扫描，交换元素后继续，直到指针相遇或者交叉。</p>

<h3 id="section-4">小数组怎么处理？</h3>

<p>随着不断的递归，待排序的子数组大小越来越小，所含元素越来越少。当子数组所含元素较少（比如说，20个）时，由于它们已经基本有序，我们改变策略，对它们改用插入排序。这也方便了三数取中策略的实现，否则我们在三数取中的时候还得特殊考虑子数组有0个、1个、2个元素的情形。当子数组多大时我们转换排序方法呢？这个最优值就依赖于体系结构了。为了找到你系统中它的最优值，请多测试！测试！测试！</p>

<h2 id="section-5">完整实现</h2>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
<span class="line-number">16</span>
<span class="line-number">17</span>
<span class="line-number">18</span>
<span class="line-number">19</span>
<span class="line-number">20</span>
<span class="line-number">21</span>
<span class="line-number">22</span>
<span class="line-number">23</span>
<span class="line-number">24</span>
<span class="line-number">25</span>
<span class="line-number">26</span>
<span class="line-number">27</span>
<span class="line-number">28</span>
<span class="line-number">29</span>
<span class="line-number">30</span>
<span class="line-number">31</span>
<span class="line-number">32</span>
<span class="line-number">33</span>
<span class="line-number">34</span>
<span class="line-number">35</span>
<span class="line-number">36</span>
<span class="line-number">37</span>
<span class="line-number">38</span>
<span class="line-number">39</span>
<span class="line-number">40</span>
<span class="line-number">41</span>
<span class="line-number">42</span>
<span class="line-number">43</span>
<span class="line-number">44</span>
<span class="line-number">45</span>
<span class="line-number">46</span>
<span class="line-number">47</span>
<span class="line-number">48</span>
<span class="line-number">49</span>
<span class="line-number">50</span>
<span class="line-number">51</span>
<span class="line-number">52</span>
<span class="line-number">53</span>
<span class="line-number">54</span>
<span class="line-number">55</span>
<span class="line-number">56</span>
<span class="line-number">57</span>
<span class="line-number">58</span>
<span class="line-number">59</span>
<span class="line-number">60</span>
<span class="line-number">61</span>
<span class="line-number">62</span>
<span class="line-number">63</span>
<span class="line-number">64</span>
<span class="line-number">65</span>
<span class="line-number">66</span>
<span class="line-number">67</span>
<span class="line-number">68</span>
<span class="line-number">69</span>
<span class="line-number">70</span>
<span class="line-number">71</span>
<span class="line-number">72</span>
<span class="line-number">73</span>
<span class="line-number">74</span>
<span class="line-number">75</span>
<span class="line-number">76</span>
<span class="line-number">77</span>
<span class="line-number">78</span>
<span class="line-number">79</span>
<span class="line-number">80</span>
<span class="line-number">81</span>
<span class="line-number">82</span>
<span class="line-number">83</span>
<span class="line-number">84</span>
<span class="line-number">85</span>
<span class="line-number">86</span>
<span class="line-number">87</span>
<span class="line-number">88</span>
<span class="line-number">89</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="cp">#define INLINE __attribute__((always_inline))</span>
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
</span><span class="line"><span class="k">class</span> <span class="nc">MyCompareOperator</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line"><span class="k">public</span><span class="o">:</span>
</span><span class="line">  <span class="n">INLINE</span> <span class="kt">bool</span> <span class="k">operator</span><span class="p">()</span> <span class="p">(</span><span class="k">const</span> <span class="n">T</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="n">T</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">a</span> <span class="o">&lt;</span> <span class="n">b</span><span class="p">;}</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="p">,</span> <span class="k">typename</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">threshold</span> <span class="o">=</span> <span class="mi">20</span><span class="o">&gt;</span>
</span><span class="line"><span class="k">class</span> <span class="nc">SoupenSort</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line"><span class="k">public</span><span class="o">:</span>
</span><span class="line">  <span class="k">static</span> <span class="kt">void</span> <span class="n">sort</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">size</span><span class="p">);</span>
</span><span class="line"><span class="k">private</span><span class="o">:</span>
</span><span class="line">  <span class="k">static</span> <span class="kt">void</span> <span class="n">sort_</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">left</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">right</span><span class="p">,</span> <span class="k">const</span> <span class="n">CompareOperator</span> <span class="o">&amp;</span><span class="n">co</span><span class="p">);</span>
</span><span class="line">  <span class="k">static</span> <span class="kt">void</span> <span class="nf">insertion_sort</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">left</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">right</span><span class="p">,</span> <span class="k">const</span> <span class="n">CompareOperator</span> <span class="o">&amp;</span><span class="n">co</span><span class="p">);</span>
</span><span class="line">  <span class="k">static</span> <span class="k">const</span> <span class="n">T</span><span class="o">&amp;</span> <span class="n">get_pivot</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">left</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">right</span><span class="p">,</span> <span class="k">const</span> <span class="n">CompareOperator</span> <span class="o">&amp;</span><span class="n">co</span><span class="p">);</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="p">,</span> <span class="k">typename</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">threshold</span><span class="o">&gt;</span>
</span><span class="line"><span class="n">INLINE</span> <span class="kt">void</span> <span class="n">SoupenSort</span><span class="o">&lt;</span><span class="n">T</span><span class="p">,</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="n">threshold</span><span class="o">&gt;::</span><span class="n">sort</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">size</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="n">CompareOperator</span> <span class="n">co</span><span class="p">;</span>
</span><span class="line">  <span class="n">sort_</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">size</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">co</span><span class="p">);</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line">
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="p">,</span> <span class="k">typename</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">threshold</span><span class="o">&gt;</span>
</span><span class="line"><span class="kt">void</span> <span class="n">SoupenSort</span><span class="o">&lt;</span><span class="n">T</span><span class="p">,</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="n">threshold</span><span class="o">&gt;::</span><span class="n">sort_</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">left</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">right</span><span class="p">,</span> <span class="k">const</span> <span class="n">CompareOperator</span> <span class="o">&amp;</span><span class="n">co</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="k">if</span><span class="p">(</span><span class="n">right</span> <span class="o">-</span> <span class="n">left</span> <span class="o">&gt;</span> <span class="n">threshold</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">    <span class="k">const</span> <span class="n">T</span><span class="o">&amp;</span> <span class="n">pivot</span> <span class="o">=</span> <span class="n">get_pivot</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="n">left</span><span class="p">,</span> <span class="n">right</span><span class="p">,</span> <span class="n">co</span><span class="p">);</span>
</span><span class="line">    <span class="kt">int64_t</span> <span class="n">i</span> <span class="o">=</span> <span class="n">left</span><span class="p">;</span>
</span><span class="line">    <span class="kt">int64_t</span> <span class="n">j</span> <span class="o">=</span> <span class="n">right</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
</span><span class="line">    <span class="k">while</span><span class="p">(</span><span class="nb">true</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">      <span class="k">do</span>
</span><span class="line">      <span class="p">{</span>
</span><span class="line">        <span class="o">++</span><span class="n">i</span><span class="p">;</span>
</span><span class="line">      <span class="p">}</span><span class="k">while</span><span class="p">(</span><span class="n">co</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">pivot</span><span class="p">));</span>
</span><span class="line">      <span class="k">do</span>
</span><span class="line">      <span class="p">{</span>
</span><span class="line">        <span class="o">--</span><span class="n">j</span><span class="p">;</span>
</span><span class="line">      <span class="p">}</span><span class="k">while</span><span class="p">(</span><span class="n">co</span><span class="p">(</span><span class="n">pivot</span><span class="p">,</span> <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="p">]));</span>
</span><span class="line">      <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">j</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">        <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span>
</span><span class="line">      <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span><span class="line">        <span class="k">break</span><span class="p">;</span>
</span><span class="line">      <span class="p">}</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">right</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]);</span><span class="c1">//restore pivot</span>
</span><span class="line">    <span class="n">sort_</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="n">left</span><span class="p">,</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">co</span><span class="p">);</span>
</span><span class="line">    <span class="n">sort_</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">right</span><span class="p">,</span> <span class="n">co</span><span class="p">);</span>
</span><span class="line">  <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span><span class="line">    <span class="n">insertion_sort</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="n">left</span><span class="p">,</span> <span class="n">right</span><span class="p">,</span> <span class="n">co</span><span class="p">);</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line">
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="p">,</span> <span class="k">typename</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">threshold</span><span class="o">&gt;</span>
</span><span class="line"><span class="n">INLINE</span> <span class="kt">void</span> <span class="n">SoupenSort</span><span class="o">&lt;</span><span class="n">T</span><span class="p">,</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="n">threshold</span><span class="o">&gt;::</span><span class="n">insertion_sort</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">left</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">right</span><span class="p">,</span> <span class="k">const</span> <span class="n">CompareOperator</span> <span class="o">&amp;</span><span class="n">co</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="kt">int64_t</span> <span class="n">begin</span> <span class="o">=</span> <span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
</span><span class="line">  <span class="kt">int64_t</span> <span class="n">end</span> <span class="o">=</span> <span class="n">right</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
</span><span class="line">  <span class="k">for</span> <span class="p">(</span><span class="kt">int64_t</span> <span class="n">i</span> <span class="o">=</span> <span class="n">begin</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">end</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">    <span class="c1">//insert data[i]. data[left to i-1] are ordered already</span>
</span><span class="line">    <span class="kt">int64_t</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
</span><span class="line">    <span class="n">T</span> <span class="n">tmp</span> <span class="o">=</span> <span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
</span><span class="line">    <span class="k">while</span><span class="p">(</span><span class="n">j</span> <span class="o">&gt;-</span><span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">co</span><span class="p">(</span><span class="n">tmp</span><span class="p">,</span> <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="p">]))</span> <span class="p">{</span>
</span><span class="line">      <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
</span><span class="line">      <span class="n">j</span><span class="o">--</span><span class="p">;</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">    <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">tmp</span><span class="p">;</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line">
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="p">,</span> <span class="k">typename</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">threshold</span><span class="o">&gt;</span>
</span><span class="line"><span class="n">INLINE</span> <span class="k">const</span> <span class="n">T</span><span class="o">&amp;</span> <span class="n">SoupenSort</span><span class="o">&lt;</span><span class="n">T</span><span class="p">,</span> <span class="n">CompareOperator</span><span class="p">,</span> <span class="n">threshold</span><span class="o">&gt;::</span><span class="n">get_pivot</span><span class="p">(</span><span class="n">T</span> <span class="o">*</span><span class="n">data</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">left</span><span class="p">,</span> <span class="kt">int64_t</span> <span class="n">right</span><span class="p">,</span> <span class="k">const</span> <span class="n">CompareOperator</span> <span class="o">&amp;</span><span class="n">co</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="kt">int64_t</span> <span class="n">mid</span> <span class="o">=</span> <span class="p">(</span><span class="n">left</span> <span class="o">+</span> <span class="n">right</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
</span><span class="line">  <span class="k">if</span> <span class="p">(</span><span class="n">co</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">mid</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">left</span><span class="p">]))</span> <span class="p">{</span>
</span><span class="line">    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">mid</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">left</span><span class="p">]);</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="k">if</span> <span class="p">(</span><span class="n">co</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">right</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">mid</span><span class="p">]))</span> <span class="p">{</span>
</span><span class="line">    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">mid</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">right</span><span class="p">]);</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="k">if</span> <span class="p">(</span><span class="n">co</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">mid</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">left</span><span class="p">]))</span> <span class="p">{</span>
</span><span class="line">    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">mid</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">left</span><span class="p">]);</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="c1">//Store pivot there to facilitate bound processing in sort_</span>
</span><span class="line">  <span class="c1">//data[right - 1] &lt;= data[right]</span>
</span><span class="line">  <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">mid</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">right</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]);</span>
</span><span class="line">  <span class="k">return</span> <span class="n">data</span><span class="p">[</span><span class="n">right</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>
<p>我们把以上实现的快速排序称为SoupenSort。是的，90行不到。</p>

<h2 id="section-6">测试结果</h2>

<p>测试程序已经放到了github上，可以从<a href="https://github.com/yebangyu/Soupen/blob/master/src/bad/test.cpp">这里</a>下载。</p>

<p>我们pk的对象包括STL中的sort，以及C语言里大名鼎鼎的qsort。</p>

<p>我们的平台是Ubuntu 64位系统 + gcc 4.8</p>

<p>测试结果：</p>

<p>1000W个随机打乱的32位无符号整数</p>

<p>开启O2优化（单位：秒）：</p>

<p>sort: 1.06</p>

<p>SoupenSort: 1.20</p>

<p>qsort: 2.08</p>

<p>未开启O2优化（单位：秒）：</p>

<p>sort: 3.29</p>

<p>SoupenSort: 2.93</p>

<p>qsort: 2.91</p>

<p>1000W个相同的整数</p>

<p>开启O2优化（单位：秒）：</p>

<p>sort: 0.23</p>

<p>SoupenSort: 0.27</p>

<p>qsort: 0.59</p>

<p>未开启O2优化（单位：秒）：</p>

<p>sort: 2.60</p>

<p>SoupenSort: 1.56</p>

<p>qsort: 0.76</p>

<p>什么结论？</p>

<p>没开优化，那么所需时间 qsort &lt; SoupenSort &lt; sort</p>

<p>开了优化，那么所需时间 sort &lt; SoupenSort &lt; qsort</p>

<p>为什么sort可以这么叼？据说它综合了插入排序、快速排序和堆排序。这让我想起了推荐和广告比赛里，有些队伍利用Ensemble Learning没节操地堆了几百个model。。。</p>

<h2 id="further-thinking">Further Thinking</h2>

<p>1，64行的 <code>while(j &gt;-1 &amp;&amp; co(tmp, data[j]))</code> 能否改为 <code>while(j &gt;-1 &amp;&amp; !co(data[j], tmp))</code> ？ 同理，36和40行能否作相应的改动？</p>

<p>2，30-46行能否改为：</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="kt">int64_t</span> <span class="n">i</span> <span class="o">=</span> <span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
</span><span class="line"><span class="kt">int64_t</span> <span class="n">j</span> <span class="o">=</span> <span class="n">right</span> <span class="o">-</span> <span class="mi">2</span><span class="p">;</span>
</span><span class="line"><span class="k">while</span><span class="p">(</span><span class="nb">true</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">  <span class="k">while</span><span class="p">(</span><span class="n">co</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">pivot</span><span class="p">))</span> <span class="p">{</span>
</span><span class="line">    <span class="o">++</span><span class="n">i</span><span class="p">;</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="k">while</span><span class="p">(</span><span class="n">co</span><span class="p">(</span><span class="n">pivot</span><span class="p">,</span> <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="p">]))</span> <span class="p">{</span>
</span><span class="line">    <span class="o">--</span><span class="n">j</span><span class="p">;</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">j</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span>
</span><span class="line">  <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span><span class="line">    <span class="k">break</span><span class="p">;</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

<p>深入分析这样的case，将会对编写正确的快速排序的困难性有更深的体会，虽然我们已经有循环不变式这个强大的工具。</p>

<p>3，快速排序所需的栈空间是多少？能否进一步优化？</p>

<p>4，SoupenSort的时间复杂度是多少？O($n^2$)还是O($nlgn$)？如果是前者，那么，什么情况下是二次的？</p>
</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Yebangyu</span></span>

      




<time class='entry-date' datetime='2016-03-09T22:34:14+08:00'><span class='date'><span class='date-month'>Mar</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:34 pm</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/suan-fa/'>算法</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  
  
</div>

    
    <p class="meta">
      
        <a class="basic-alignment left" href="/blog/2016/03/04/petersonalgorithm/" title="Previous Post: Peterson算法实现spin lock">&laquo; Peterson算法实现spin lock</a>
      
      
        <a class="basic-alignment right" href="/blog/2016/03/25/fuckthefever/" title="Next Post: C99中的柔性数组">C99中的柔性数组 &raquo;</a>
      
    </p>
  </footer>
</article>


</div>

<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
